1. Field of the Invention
Methods consistent with the present invention relate to a beacon scheduling in multi-hop ad-hoc communications. More particularly, the present invention relates to a beacon scheduling method in multi-hop ad-hoc communications for preventing overhead in a manner that a base station (BS) transmits beacon slot information to a carrier sense multiple access (CSMA)/collision avoidance (CA) node (CN) and a gateway (GW) through contention-free time division multiple access (TDMA) communications at an initial clustering, the CN and the GW perform sequential clustering to forward the beacon slot information to a cluster head (CH), the CH aggregates joining messages from nodes and assigns non-colliding beacon slots to the nodes, and the GW uses a beacon slot frame of a beacon transmission period (BTP) used by its selected CH in a beacon reply period (BRP) as well.
2. Description of the Related Art
Generally, a wireless personal area network (WPAN) adopts the hierarchical routing based on clusters more frequently than flat routing.
To avoid collisions among center nodes within a cluster, the cluster-based hierarchical routing classifies communications schemes between sensor nodes and the cluster head largely into a time division multiple access (TDMA) scheme based on the reserved allocation and a carrier sense multiple access (CSMA)/collision avoidance (CA) based on contention.
FIG. 1A depicts the reservation-based TDMA scheme using a single frequency channel.
As shown in FIG. 1A, a fundamental unit of the WPAN is a piconet consisting of a sole piconet coordinator (PC) and more than one mobile device (DEV) which shares a unique network identifier. The PC forms a piconet and provides a basic communicating timing by transmitting a beacon, and provides wireless communication services such as quality of service (QoS), synchronization, a power saving mode, and media access control (MAC) with respect to piconet devices in its coverage area.
According to IEEE 802.15.3 standard, the piconet is arbitrarily established if necessary. In the piconet, a plurality of devices independently shares a sole medium using a peer-to-peer technology and communicates with one another using a multi-hop scheme. Such a piconet is called an ad-hoc network. The multi-hop scheme delivers packets originated from a source node to a destination node by way of a plurality of mobile devices which act as both a host and a router in communications among mobile devices over the ad-hoc network. Since the transmission range of the wireless propagation in the piconet is limited to 10m at maximum, the packets may not be delivered from the source node directly to the destination node on occasion.
As such, the plurality of devices in the piconet share the sole medium for communications. Hence, to avoid collisions during communications between the devices, each device is allowed to communicate at an appropriate time by controlling the devices' access to the medium. As shown in FIG. 1A, data are transmitted among the sensor nodes without collisions by reserving and allocating timings T1, T2 and T3 to each cluster in the same frequency channel.
However, the TDMA scheme inevitably encounters intercluster interference in a multi-cluster environment. In more detail, when sensor nodes located in an overlapping area between adjacent clusters transmit data, other sensor nodes transmitting data in a neighboring cluster may be interfered with. Thus, the multi-frequency channel is required to avoid the interference between the piconets in the hierarchical structure.
FIG. 1B depicts the contention-based CSMA/CA by use of a single frequency channel.
As shown in FIG. 1B, the contention-based CSMA/CA scheme allows the data transmission between the sensor nodes without collisions by sending a request to send (RTS)/clear to send (CTS) signal between a cluster head (CH) and a sensor node within the cluster. However, since the data is broadcast in the single frequency channel, collisions between nodes drastically increase as the number of sensor nodes increases. Accordingly, the number of data retransmissions also increases and more beacon slots are required to reduce the collisions.
FIG. 1C depicts beacon collisions in a beacon transmission period (BTP) and a beacon relay period (BRP).
Referring to FIG. 1C, a beacon and a query are transmitted in the BTP and the BRP. The CH or a base station (BS) transmits in the BTP, and a first gateway GW1 transmits in the BRP.
Specifically, the CH or the BS transmits the beacon and the query to the GW1, a TDMA node (TN), and a CSMA/CA node (CN) in the BTP of the first frame. In response to this, GW1 and GW2, upon receiving the beacon and the query from the CH or the BS, send a beacon and a query to neighboring CH1 and CH2 in the BRP of the first frame.
A plurality of CHs broadcast the beacon and the query in the BTP. At this time, since the CHs are two hops away, it is impossible to avoid the collision through active and passive scanning. When a plurality of GWs unicast the beacon and the query to the CH in the BRP, it is also impossible to avoid the collision through the active and passive scanning since the GWs are away from one another by one or two hops. Furthermore, the beacon information is delayed, and the CH and the GW require additional energy consumption.